package formal.tree.recursion;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 左叶子之和
 *
 * @author DengYuan2
 * @create 2021-01-16 16:08
 */
public class E_404 {
    public static void main(String[] args) {
        Integer[] a = {3, 9, 20, null, null, 15, 7};
        TreeNode treeNode = TreeNode.generateTree(a);
        int res = sumOfLeftLeaves3(treeNode);
        System.out.println(res);
    }

    /**
     * 我的写法-递归
     *
     * @param root
     * @return
     */
    public static int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return sumHelper(root.left, true) + sumHelper(root.right, false);
    }

    public static int sumHelper(TreeNode node, boolean isLeft) {
        if (node == null) {
            return 0;
        }
        int sum = 0;
        if (isLeft) {
            if (node.left == null && node.right == null) {
                sum += node.val;
                return sum;
            }
        }

        return sum + sumHelper(node.left, true) + sumHelper(node.right, false);
    }

    /**
     * 大神-递归-与官方的思路一致，写法不一致
     *
     * @param root
     * @return
     */
    public static int sumOfLeftLeaves2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (isLeave(root.left)) {
            return root.left.val + sumOfLeftLeaves2(root.right);
        }
        return sumOfLeftLeaves2(root.left) + sumOfLeftLeaves2(root.right);
    }

    public static boolean isLeave(TreeNode node) {
        if (node == null) {
            return false;
        }
        if (node.left == null && node.right == null) {
            return true;
        }
        return false;
    }

    public static int sumOfLeftLeaves3(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int sum = 0;
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            if (poll.left != null) {
                if (isLeave(poll.left)) {
                    sum += poll.left.val;
                } else {
                    queue.offer(poll.left);
                }
            }
            if (poll.right != null) {
                queue.offer(poll.right);
            }
        }
        return sum;
    }
}
